package java学习.算法.排序;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/6/9 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 数组中的逆序对 {
    /*
    在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
    输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
     */
    public static void main(String[] args) {
        int[]arr={1,2,3,4,5,6,7,0};
        int n = arr.length;
//        System.out.println(InversePairs(arr));
        int [] temp = new int[arr.length];
        System.out.println(func(arr,0,n-1,temp));
    }

    // O(n2)写法
    public static int InversePairs(int [] array) {
        int n = array.length;
        int c = 0;
        for (int i = 0; i <n ; i++) {
            for (int j = i+1; j < n  ; j++) {
                if (array[i]>array[j]){
                    c++;
                }
            }

        }
        System.out.println("逆序对个数"+c);
//        return Math.floorMod(1,1000000007);
        return c%1000000007;
    }

//  归并排序

    private static int func(int[] arr, int l,   int r, int[] temp) {
        if (l==r) return 0;
        int mid = l + (r-l)/2;
        int lcount = func(arr,l,mid,temp);
        int rcount = func(arr,mid+1,r,temp);
        int curCount = merge(l,mid,r,arr,temp);
        return lcount+rcount+curCount;

    }

    /**
     *  计算当前两个子数组合并成一大数组的 逆序对的个数。
     * @param l
     * @param mid
     * @param r
     * @param arr
     * @param temp
     * @return
     */
    private static int merge(int l, int mid, int r, int[] arr, int[] temp) {
//        将 arr的数组操作 arr 的元素
        for(int i = l; i<=r;i++){
            temp[i] = arr[i];
        }
//        准备两个指针： i j 分别指向两个子数组的头：
        int i = l , j = mid+1;
        int count = 0;
        for (int k = l;k<=r;k++){
            if (i==mid+1){          // 出现i超过mid 说明此时前面的子数组已经完了，直接将后面的数组直接挪到arr
                arr[k] = temp[j];
                j++;
            }else if (j == r+1){   // 后面的数组的元素完了， 直接将前面的数组直接挪到arr
                arr[k] = temp[i];
                i++;
            } else  if (temp[i]>temp[j]){ // 则temp[j] 就小于 temp[i]数组的全部元素，与之构成逆序对。
                arr[k] = temp[j];
                j++;
                count+=(mid-i)+1;  // 此时都是mid之前的元素，故拿mid-i去算

            }else {             // 则temp[i] 就小于 temp[j]数组的全部元素,有序诶,不记录
                arr[k] = temp[i];
                i++;
            }

        }
            return count;

    }


}
